/**
 * 给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums ：
 *
 * nums[0] = 0
 * nums[1] = 1
 * 当 2 <= 2 * i <= n 时，nums[2 * i] = nums[i]
 * 当 2 <= 2 * i + 1 <= n 时，nums[2 * i + 1] = nums[i] + nums[i + 1]
 * 返回生成数组 nums 中的 最大 值。
 */
public class Test1646 {
    public int getMaximumGenerated(int n) {
        if (n == 0) return 0;
        int[] ret = new int[n+1];
        ret[0] = 0;
        ret[1] = 1;
        for (int i = 1; i < n; i++) {
            if (2 <= 2 * i  && 2 * i <= n){
                ret[2*i] = ret[i];
            }
            if (2 <= 2 * i + 1  && 2 * i + 1 <= n){
                ret[2 * i + 1] = ret[i] + ret[i + 1];
            }
        }

        int max = ret[0];
        for (int i = 1; i < ret.length; i++) {
            max = Math.max(max,ret[i]);
        }
        return max;
    }
}
